In many wireless communications systems, convolutional coding is used to enable correction of errors in received symbols due to transmission distortions such as noise. A commonly used process for decoding convolutionally encoded symbols is the Viterbi decoding process. Errors in the received symbols may be corrected since redundancy is added to the transmitted, convolutional by encoded symbols. This is referred to as channel coding. Error correction is influenced by a number of parameters, one being the number of past samples that is used to form the current sample. This is referred to as the constraint length k, and equals the number of unit delay elements included in the encoder plus one. The constraint length represents the total span of past samples used to form the current sample. The number of states of a convolutional coder is determined by the number of unit delay elements. In practice, a coder having a constraint length k is implemented by means of a (k−1)-stage shift register where selected outputs are added to form the encoded symbols. Consequently, the number of possible states is 2k-1. Hence, a three-bit shift register can produce eight different states (and has a constraint length k of four). Another important parameter is the coding rate R, which is defined as the ratio of input bits to output bits of the coder. Hence, for a coding rate of 1/3, three output bits are transmitted for each input bit, i.e. each input bit forms an output symbol that comprises three bits.
Allowable state transitions of the coder are represented by a trellis diagram. The states represent the actual bit content in the shift register and the state transitions represent the output symbols associated with a certain input. The state transitions also define the path of the trellis. Viterbi decoding starts only after a certain number of encoded symbol has been received, whereby the coder has undergone a number of state transitions and a corresponding number of trellis paths have been created. The Viterbi decoding process provides a method for finding the most probable path through the trellis of state transitions while minimizing the number of trellis paths. This is done by calculating the most likely previous state for all coder states. The most likely previous state is estimated by combining the current input value and the accumulated path metrics of the previous states. Since each state has two or more possible input paths, an accumulated distance is calculated for each input path. The path with the minimum accumulated distance is selected as the most likely path. This minimum path is traced back to its beginning, and the traced-back symbol sequence becomes the decoded signal. Some convolution coders (coders having a coding rate of 1/n) have the advantage that their trellis diagrams can be divided into small groups, so called butterflies. By exploiting butterfly symmetry in the trellis diagram, the number of path metric calculations can be reduced. The butterfly arrangement has the advantage that prior accumulated metrics (i.e. old metric values) are the same for the updates of both new states, which minimizes address manipulations.
In the prior art Viterbi decoding process, metric update is typically performed by using four buffers for each butterfly, two input (read) buffers and two output (write) buffers. The read buffers comprise the old accumulated metrics and the write buffers comprise the new metrics. The total size of the buffers is 2k-1 words, is equal to the number of delay states. Hence, the size of each buffer is 2k-1/4.
Reading/writing is made from/to these different buffers, and for each state transition the read buffers are updated. A problem associated with this approach is that each new path metric must be stored at the correct memory location because the path metrics are linked, or associated, to each other with pointers. The old metrics are accessed in consecutive order, i.e. the order of the metrics are important for the decoding process, and pointers are employed to maintain the order of the metrics.
FIG. 1 shows a prior art addressing architecture for a Viterbi decoding process where metric update is typically performed by using four buffers 101, 102, 103, 104 (and 111, 112, 113, 114) for each butterfly 115 (and 125). These four buffers comprises two input (read) buffers 103, 104 and two output (write) buffers 101, 102. The read buffers comprise the old accumulated metrics and the write buffers comprise the new metrics. As mentioned previously, when using this addressing approach, new path metric must be stored at the correct memory location because the path metrics are associated to each other with pointers. The old metrics are accessed in consecutive order, and pointers are employed to maintain the order of the metrics.